package mrHunter.puzzles.graph;

public class Puzzle2 {
    //shortest path
    public class Dis{
        boolean visit;
        int value;
        String path;
    }

    public String shortestPath(String input){
        String[] inputs=input.split(",");
        int startV=Integer.parseInt(inputs[1]);
        int endV=Integer.parseInt(inputs[2]);
        String[] rows=inputs[0].split("%");
        int vNum=rows.length;
        int[][] edges=new int[vNum][vNum];
        for(int i=0;i<vNum;i++){
            String[] cols=rows[i].split(" ");
            for(int j=0;j<vNum;j++){
                edges[i][j]=Integer.parseInt(cols[j]);
            }
        }
        return dijkstra(startV,endV,edges);
    }

    public String dijkstra(int startV, int endV, int[][] edges){
        int vNum=edges[0].length;
        Dis[] dis=new Dis[vNum];
        for(int i=0;i<vNum;i++){
            dis[i]=new Dis();
            dis[i].value=Integer.MAX_VALUE;
            if(edges[startV][i]!=0)
                dis[i].value=edges[startV][i];
            dis[i].visit=false;
            dis[i].path="";
        }
        dis[startV].value=0;
        dis[startV].visit=true;
        int count=0;
        while (count<vNum-1){
            //temp: 保存当前dis数组中最小的下标
            int temp=0;
            int min=Integer.MAX_VALUE;
            for(int i=0;i<vNum;i++){
                if((!dis[i].visit)&&(dis[i].value<min)){
                    min=dis[i].value;
                    temp=i;
                }
            }
            dis[temp].visit=true;
            count++;
            for(int i=0;i<vNum;i++){
                if((!dis[i].visit)&&(edges[temp][i]!= 0)&&((dis[temp].value+edges[temp][i])<dis[i].value)){
                    dis[i].value=dis[temp].value+edges[temp][i];
                    dis[i].path=dis[temp].path+" "+String.valueOf(temp);
                }
            }
        }
        StringBuilder res=new StringBuilder();
        res.append(String.valueOf(dis[endV].value));
        res.append(",");
        res.append(String.valueOf(startV)).append(" ").append(endV);

        return res.toString();
    }
}
